#include <stdio.h>
#include <stdlib.h>
#include "../1_bin_tree/creat.h"
void insert(tree *&root, int key)
{
    if (!root)
    {
        root = (tree *)malloc(sizeof(tree));
        root->data = key;
        root->left = root->right = NULL;
    }
    else
    {
        if (root->data > key)
        {
            insert(root->left, key);
        }
        else if (root->data == key)
        {
            return;
        }
        else
        {
            insert(root->right, key);
        }
    }
}
tree *creat_sort_tree(int a[], int n)
{
    tree *root = NULL;
    for (int i = 0; i < n; i++)
        insert(root, a[i]);
    return root;
}

tree *search_key(tree *root, int key)
{
    tree *p = root;
    while (p)
    {
        if (p->data > key)
        {
            p = p->left;
        }
        else if (p->data == key)
        {
            return p;
        }
        else
        {
            p = p->right;
        }
    }
    return NULL;
}
void delet(tree *&node)
{
    tree *p, *t;
    if (!node->left)
    {
        p = node;
        node = node->right;
        free(p);
    }
    else if (!node->right)
    {
        p = node;
        node = node->left;
        free(p);
    }
    else
    {
        p = node;
        t = node->right;
        while (t->left)
        {
            p = t;
            t = t->left;
        }
        node->data = t->data;
        if (p != node)
        {
            p->left = t->right;
        }
        else
        {
            p->right = t->right;
        }
        free(t);
    }
}
void delete_node(tree *&root, int key)
{
    if (root)
    {
        if (root->data == key)
        {
            delet(root);
        }
        else if (root->data > key)
        {
            delete_node(root->left, key);
        }
        else if (root->data < key)
        {
            delete_node(root->right, key);
        }
    }
}
int main()
{
    /*******************code*******************/
    int n = 10;
    int a[] = {5, 4, 7, 3, 6, 8, 9, 1, 2, 0};
    tree *root = creat_sort_tree(a, n);
    midorder_traversal(root);
    printf("\n");
    delete_node(root, 5);
    midorder_traversal(root);
    printf("\n");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}

// bool deleteNode(tree **b)
// {
//     tree *p, *s;
//     if ((*b)->left == NULL)
//     {
//         p = (*b);
//         (*b) = (*b)->right;
//         free(p);
//     }
//     else if ((*b)->right == NULL)
//     {
//         p = (*b);
//         (*b) = (*b)->left;
//         free(p);
//     }
//     else
//     {
//         p = (*b);
//         s = (*b)->left;
//         while (s->right != NULL)
//         {
//             p = s;
//             s = s->right;
//         }
//         (*b)->data = s->data;
//         if (p != (*b))
//             p->right = s->left;
//         else
//             p->left = s->left;
//         free(s);
//         return true;
//     }
// }
// bool deleteTree(tree **b, int key)
// {
//     if (!*b)
//         return false;
//     else
//     {
//         if ((*b)->data == key)
//         {
//             return deleteNode(&(*b));
//         }
//         else if ((*b)->data > key)
//             return deleteTree(&(*b)->left, key);
//         else
//             return deleteTree(&(*b)->right, key);
//     }
// }